// 解题思路：
// 初始汽油为 0，从 i 位置出发，可以获得 gas[i] 升的汽油，到下一个地点需要消耗 cost[i] 升的汽油，从哪个位置出发可以旅行一圈？
// 暴力解法：
// 遍历起点，模拟是否能够旅行一圈，如果中间汽油的余量 < 0，则不能旅行一圈，如果一直 >= 0，则可以旅行一圈
// 难点：如何让走到最后一个位置 n - 1 的下一个位置是 0？
// 可以定义一个 step，表示从 i 位置出发，走了 step 步， 0 <= step < n;
// ((n - 1) + 1) % n == 0，因此只要模上一个 n 即可
// step 走到原点前一个位置后，减去出发用掉的汽油，余量大于等于 0 就表示能环游一周

// 优化：
// 当内循环结束，如果余量小于 0，就表示出发点 i 到 当前位置 i + step，中间从哪个点出发都到不了终点
// 因为从 i 出发的时候肯定余量 >= 0 的，走到后面余量减少，因此从 i 后面的位置余量是一直减少的，直接从 i + step + 1 的位置尝试即可

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for(int i = 0; i < n; i++){
            int rest = 0;
            int step = 0;
            for( ; step < n; step++){
                int index = (i + step) % n;
                rest += gas[index];
                rest -= cost[index];
                if(rest < 0){
                    break;
                }
            }
            if(rest >= 0){
                return i;
            }
            i = i + step;
        }
        return -1;
    }
}
